|
In the mathematical field of graph theory, the Rado graph, also known as the random graph or the Erdős–Rényi graph, is the unique (up to isomorphism) countably infinite graph ''R'' such that for every finite graph ''G'' and every vertex ''v'' of ''G'', every embedding of ''G'' − ''v'' as an induced subgraph of ''R'' can be extended to an embedding of ''G'' into ''R''. As a consequence of this property, the Rado graph contains all finite and countably infinite graphs as induced subgraphs. It is named after Richard Rado, Paul Erdős, and Alfréd Rényi, who all studied it in the early 1960s, but it appears even earlier in the work of . The Rado graph can be constructed by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or by connecting two prime numbers that are congruent to 1 mod 4 when one is a quadratic residue modulo the other. It can also be constructed, with high probability, by a random process on a countably infinite number of vertices in which each pair of vertices has independent probability 1/2 of being connected by an edge. The first-order logic sentences that are true of the Rado graph are also true of almost all random finite graphs, and the sentences that are false for the Rado graph are also false for almost all finite graphs. In model theory, the Rado graph forms an example of a saturated model of an ω-categorical and complete theory. ==History== The Rado graph was first constructed by in two ways, with vertices either the hereditarily finite sets or the natural numbers. (Strictly speaking Ackermann described a directed graph, and the Rado graph is the corresponding undirected graph given by forgetting the directions on the edges.) constructed the Rado graph as the random graph on a countable number of points. They proved that it has infinitely many automorphisms, and their argument also shows that it is unique though they did not mention this explicitly. rediscovered the Rado graph as a universal graph, and gave an explicit construction of it with vertex set the natural numbers essentially equivalent to one of Ackermann's constructions. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Rado graph」の詳細全文を読む スポンサード リンク
|